#pragma once

#include <vector>
using namespace std;

class UnionFind
{
public:
	UnionFind(size_t n)
		:_ufs(n, -1)
	{}
	void Union(int a, int b)
	{
		int root1 = FindRoot(a), root2 = FindRoot(b);
		if (root1 == root2) return;
		if (_ufs[root1] < _ufs[root2])
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
		else
		{
			_ufs[root2] += _ufs[root1];
			_ufs[root1] = root2;
		}
	}
	int FindRoot(int x)
	{
		int root = x, parent = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
			_ufs[x] = root;
			x = parent;
		}
		return root;
	}
	bool Inset(int a, int b)
	{
		return FindRoot(a) == FindRoot(b);
	}
	size_t SetSize()
	{
		int ret = 0;
		for (auto i : _ufs) if (i < 0) ret++;
		return ret;
	}
private:
	vector<int> _ufs;
};

void TestUnionFindSet()
{
	UnionFind ufs(10);
	ufs.Union(8, 9);
	ufs.Union(7, 8);
	ufs.Union(6, 7);
	ufs.Union(5, 6);
	ufs.Union(4, 5);

	ufs.FindRoot(6);
	ufs.FindRoot(9);
}